package LeetCode.month02.day32;

import java.util.Arrays;
import java.util.HashMap;

public class No2555 {
    public static void main(String[] args) {
        System.out.println(maximizeWin(new int[]{1,3,4,5,7,11,13,14,15},2));
    }
    public static int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions.length;
        int[] max = new int[n+1];
        max[0]=0;
        if(k*2+1>=prizePositions[n-1]-prizePositions[0]) return n;
        int res = 0;
        int left =0;
        for (int right = 0; right < n; right++) {
            while(prizePositions[right]-prizePositions[left]>k){
                left++;
            }
            res = Math.max(res,max[left]+right-left+1);
            max[right+1] = Math.max(max[right],right-left+1);
        }
        return res;
    }
}
